#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Mon Jul 10 13:20:40 2023

@author: liqingsimac
"""
#'''
##########################################
##Dijkstra by hand:
import numpy as np
aa=np.inf
R1=[0, 6, 3, 1, aa, aa, aa, aa, aa]
R2=[aa, 0, aa, aa, 1, aa, aa, aa, aa]
R3=[aa, 2, 0, 2, aa, aa, aa, aa, aa]
R4=[aa, aa, aa, 0, aa, 10, aa, aa, aa]
R5=[aa, aa, aa, 6, 0, 4, 3, 6, aa]
R6=[aa, aa, aa, aa, 10, 0, 2, aa, aa]
R7=[aa, aa, aa, aa, aa, aa, 0, 4, aa]
R8=[aa, aa, aa, aa, aa, aa, aa, 0, aa]
R9=[aa, aa, aa, aa, 2, aa, aa, 3, 0]


W=np.array([R1,R2,R3,R4,R5,R6,R7,R8,R9])

ell=[0,aa,aa,aa,aa,aa,aa,aa,aa] #从顶点1到每个顶点的当前路径的长度
z=[0,0,0,0,0,0,0,0,0] #保存每个顶点的父顶点
V={0,1,2,3,4,5,6,7,8} #所有顶点的集合
S={0} #永久顶点集
SL=[0]
ii=0

for ii in range(9):
#    print('Iteration number:', ii)
    print('第%d次循环'%ii,'：')
    print('永久顶点集：',SL)
    print('从顶点0到每个顶点的当前路径的长度：',ell)
    print('每个顶点的父顶点：', z)
    print('\n')    
    for v in V-S:
        for u in S:
            if ell[u]+W[u,v]<ell[v]:
                z[v]=u; ell[v]=ell[u]+W[u,v]
    temp=aa; change=0
    for v in V-S:
        if ell[v]<temp:
            change=1; ni=v; temp=ell[v]
    if change==1:
        S.add(ni); SL.append(ni)

##########################################
#'''


'''
##########################################
##Dijkstra by networkx:
#程序文件ex6_7.py
import networkx as nx

G = nx.DiGraph()
List = [(1,2,6), (1,3,3), (1,4,1), (2,5,1), (3,2,2), (3,4,2), (4,6,10), (5,4,6),
        (5,6,4), (5,7,3), (5,8,6), (6,5,10), (6,7,2), (7,8,4), (9,5,2), (9,8,3)]
G.add_nodes_from(range(1,10))
G.add_weighted_edges_from(List)
path = nx.dijkstra_path(G, 1, 8, weight='weight')  #求最短路径
d = nx.dijkstra_path_length(G, 1, 8, weight='weight')
print('最短路径为：', path)
print('最小费用为：', d)    

##########################################
'''

'''
##########################################
##Dijkstra by zhihu:
def startwith(start: int, mgraph: list) -> list:
    passed = [start]
    nopass = [x for x in range(len(mgraph)) if x != start]
    dis = mgraph[start]
    
    while len(nopass):
        idx = nopass[0]
        for i in nopass:
            if dis[i] < dis[idx]: idx = i

        nopass.remove(idx)
        passed.append(idx)

        for i in nopass:
            if dis[idx] + mgraph[idx][i] < dis[i]: dis[i] = dis[idx] + mgraph[idx][i]
    return dis


if __name__ == "__main__":
    inf = 10086
    mgraph = [[0, 1, 12, inf, inf, inf],
              [inf, 0, 9, 3, inf, inf],
              [inf, inf, 0, inf, 5, inf],
              [inf, inf, 4, 0, 13, 15],
              [inf, inf, inf ,inf, 0, 4],
              [inf, inf, inf, inf ,inf, 0]]

    dis = startwith(0, mgraph)
##########################################
'''

'''
##########################################
#import numpy as np
aa=999
kgraph=[[0, 6, 3, 1, aa, aa, aa, aa, aa],
[aa, 0, aa, aa, 1, aa, aa, aa, aa],
[aa, 2, 0, 2, aa, aa, aa, aa, aa],
[aa, aa, aa, 0, aa, 10, aa, aa, aa],
[aa, aa, aa, 6, 0, 4, 3, 6, aa],
[aa, aa, aa, aa, 10, 0, 2, aa, aa],
[aa, aa, aa, aa, aa, aa, 0, 4, aa],
[aa, aa, aa, aa, aa, aa, aa, 0, aa],
[aa, aa, aa, aa, 2, aa, aa, 3, 0]]

kdis=startwith(0, kgraph)
##########################################
'''

